 d#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+10;
int n,m,sq,pos[MAXN],a[MAXN],_map[MAXN],pre[MAXN],cnt,ans[MAXN];
struct query
{
	int l,r,num;
	bool operator<(const query b)const
	{
		return pos[l]==pos[b.l]?r<b.r:pos[l]<pos[b.l];
	}
}qu[MAXN];
int lowbit(int x)
{
	return x&-x;
}
int query(int o)
{
	int ans=0;
	while(o)
	{
		ans+=pre[o];
		o-=lowbit(o);
	}
	return ans;
}
void update(int o,int x)
{
	while(o<=n)
	{
		pre[o]+=x;
		o+=lowbit(o);
	}
	return;
}
int main()
{
	scanf("%d",&n);
	sq=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		_map[i]=a[i];
		pos[i]=(i-1)/sq+1;
	}
	sort(_map+1,_map+1+n);
	for(int i=1;i<=n;++i)a[i]=lower_bound(_map+1,_map+1+n,a[i])-_map;
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&qu[i].l,&qu[i].r);
		qu[i].num=i;
	}
	sort(qu+1,qu+1+m);
	int l=1,r=0;
	for(int i=1;i<=m;++i)
	{
		while(r<qu[i].r)
		{
			++r;
			update(a[r],1);
			cnt+=r-l+1-query(a[r]);
		}
		while(l>qu[i].l)
		{
			--l;
			update(a[l],1);
			cnt+=query(a[l]-1);
		}
		while(r>qu[i].r)
		{
			update(a[r],-1);
			cnt-=r-l-query(a[r]);
			--r;
		}
		while(l<qu[i].l)
		{
			update(a[l],-1);
			cnt-=query(a[l]-1);
			++l;
		}
		ans[qu[i].num]=cnt;
	}
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}
